import java.util.ArrayList;
import java.util.List;

public class Test1 {
    //leetcode 路经总和II
    //https://leetcode.cn/problems/path-sum-ii/
    List<List<Integer>> ret;
    List<Integer> path;
    int sum;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        path = new ArrayList<>();
        backTracing(root,targetSum);
        return ret;
    }

    private void backTracing(TreeNode root,int targetSum) {
        if (root == null) return;
        path.add(root.val);
        sum += root.val;
        if (root.left == null && root.right == null && sum == targetSum) {
            ret.add(new ArrayList(path));
        }
        backTracing(root.left,targetSum);
        backTracing(root.right,targetSum);
        path.remove(path.size()-1);
        sum -= root.val;
    }
}
